The present invention relates to a network routing apparatus. It particularly relates to a network routing apparatus which is adapted to a network routing apparatus such as a router, a repeater, or the like, in a computer network system and which can retrieve a forwarding address of an input packet at a high speed.
A network routing apparatus such as a router, a bridge, or the like, is generally used for connecting a plurality of networks to one another in a network system. The router examines a destination address of a packet received from a connected network to thereby determine the forwarding address of the packet and forwards the packet to a network to which a router or host of the forwarding address is connected.
Whenever the router receives a packet from a network interface board, the router determines a packet output interface on the basis of the destination information contained in header information of the packet, further determines a forwarding host or router out of hosts or routers connected to the packet output interface, and forwards the packet to the determined host or router. A higher-functional router performs, in addition to the function of forwarding the packet, a function (filtering function) for aborting a packet in accordance with the header conditions of the packets, a function (priority control function) for determining output priority of a plurality of packets to output the packets in the order of priority of the plurality of packets when such packets are to be forwarded, a function for rewriting Type of Service (ToS) contained in the header information of the packet, and so on.
Generally, the router further has a statistical function for counting the number of packets forwarded, the number of bytes forwarded, the number of packets aborted by filtering in the router or by traffic congestion of packets in the router, the number of (non-routed) packets undefined in terms of output destination as a result of retrieval (routing retrieval) of output addresses of packets, the number of packets addressed to the router itself, the number of packets satisfying the aborting condition of filtering, and so on. These pieces of statistical information are displayed on a terminal for managing router operations or router status indication, or the like, or these pieces of statistical information are sent to a network management apparatus in a network so as to be used for management of the network.
Functions other than the statistical function may be required as follows, in the case where the number of packet data transfer bytes needs to be measured. When, for example, a network provider receives packets from users, the packets are classified into several groups (hereinafter referred to as “flows”) (for example, according to source/destination sub-network, TCP/IP port number, address, etc.) on the basis of the header conditions of the packets. The data transfer rate of each flow is monitored whenever this classification is made. When the data transfer rate in this flow is too high, packets sent from the users in the flow over the bandwidth on the basis of contracts between the network provider and the users may be aborted or preferentially aborted at the time of traffic congestion. This function is called “bandwidth policing function”. Further, when network users transmit packets to a network of a network provider, the output rate of packet data belonging to the flow of the network provider may be limited, by a router, within the bandwidth on the basis of a contract between the router and the network provider. This function is called “shaping function”. To achieve the bandwidth policing function or the shaping function, the number of data transfer bytes (data transfer rate) of packets flowing in the router needs to be measured at intervals of a predetermined time.
Processing in a router is classified into the aforementioned process which needs to be performed whenever a packet enters the router, a process in which routing information in a network system is transferred between routers so that a routing table is generated in the router, and a process which need not be performed whenever a packet such as statistical information of the router transferred between the router and a network management apparatus enters the router.
The aforementioned processing in a router is heretofore carried out by executing software processing. To improve performance of processing required whenever a packet enters a router, a plurality of units (RPs: Routing Processors) for performing this processing are provided in the router. Network inter-face boards are connected to the RPs correspondingly and respectively. The RPs are connected to one another through a bus or through a cross bar switch so that packets are forwarded between network interface boards connecting individual RPs, respectively. In this manner, high-speed processing in the router is attained. An example of the aforementioned router is an apparatus that is disclosed in U.S. Pat. No. 5,434,863 (JP-A-5-199230).
Traffic flowing in a network has, however, increased so that the routing process needs to be performed at a higher speed. As a result, software processing used for achieving the routing process has been replaced by hardware processing.